package gold.digger;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC1138 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {

        public Map<String, String> dict = new HashMap<>();

        public String alphabetBoardPath(String target) {
            StringBuilder res = new StringBuilder();
            char cur = 'a', next = target.charAt(0);
            findPath(cur, next, res);
            for (int i = 1; i < target.length(); i++) {
                cur = next;
                next = target.charAt(i);
                findPath(cur, next, res);
            }

            return res.toString();
        }

        public void findPath(char cur, char next, StringBuilder res) {
            if (cur == next) {
                res.append("!");
                return;
            }

            String key = String.valueOf(cur) + String.valueOf(next);
            if (dict.containsKey(key)) {
                res.append(dict.get(key));
                res.append("!");
                return;
            }

            StringBuilder curRes = new StringBuilder();
            int row = (cur - 'a') / 5, nextRow = (next - 'a') / 5;
            int col = (cur - 'a') % 5, nextCol = (next - 'a') % 5;

            if ('z' == next) {
                int count = Math.abs(nextCol - col);
                while ((count--) > 0) curRes.append(nextCol > col ? 'R' : 'L');
                count = Math.abs(nextRow - row);
                while ((count--) > 0) curRes.append(nextRow > row ? 'D' : 'U');
            } else {
                int count = Math.abs(row - nextRow);
                while ((count--) > 0) curRes.append(nextRow > row ? 'D' : 'U');
                count = Math.abs(col - nextCol);
                while ((count--) > 0) curRes.append(nextCol > col ? 'R' : 'L');
            }

            dict.put(key, curRes.toString());
            res.append(curRes.toString());
            res.append("!");
        }
    }

    // Input: target = "code"
//Output: "RR!DDRR!UUL!R!"

    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.alphabetBoardPath("code"));
    }

    public static void main(String[] args) throws Exception {
        LC1138 an = new LC1138();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
